import java.util.Arrays;
import java.util.Comparator;

/**
 * @author hewei
 * @version 1.0
 * @description: 1048. 最长字符串链
 * @date 2022/10/20 20:53
 */

public class LongestStrChain {

    public int longestStrChain(String[] words) {
        Arrays.sort(words, Comparator.comparingInt(String::length));
        int n = words.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int ans = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (check(words[j], words[i])) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }

    public boolean check(String s1, String s2) {
        if (s2.length() - s1.length() != 1) return false;
        int l1 = 0;
        int l2 = 0;
        int count = 0;
        while (l1 < s1.length()) {
            char c1 = s1.charAt(l1);
            char c2 = s2.charAt(l2);
            if (c1 == c2) {
                ++l1;
            } else {
                if (count == 1) return false;
                ++count;
            }
            ++l2;
        }
        return true;
    }
}
